1. Field of the Invention
The present invention relates, generally, to digital communications and, more particularly, to the use of convolutional interleavers for forward error correction (FEC) in digital systems. More particularly, an efficient memory scheme for convolutional interleaving is disclosed.
2. Background Art
In digital communication systems, for example, in the context of digital subscriber line technology (xDSL, ADSL, VDSL etc.), it is desirable to provide reliable and robust error correction capability. One popular method of providing error correction involves the use of Reed-Solomon (R-S) code in conjunction with a convolutional interleaver. The purpose of the is combination of R-S code and interleaving is to spread bursts of errors such that adjacent bytes in the transmitted data stream do not originate from the same codeword; thus, it reduces the number of errors in any one codeword to what can be corrected by the R-S decoder (usually half of the number of redundant check bytes added in the code). The data bytes are then reordered at the receiver by a de-interleaver.
Two important parameters which characterize an interleaver are the number of bytes per interleaving block length, N, and the interleaver depth, D, which is defined as the minimum separation at the output of the interleaver of any two input bytes in the same codeword. N can be chosen to be the same length as, or a fractional length of, the R-S codeword. In this application, we will assume N is the same as the R-S codeword length. It will be appreciated, however, that the present invention is not so limited.
There are two main interleaving methods: block interleaving and convolutional interleaving. Both types of interleaving change the order of the transmitted bytes of an outgoing stream, but do so in a deterministic fashion so that the stream can be restored upon receipt. Block interleaving fills in a fixed-size block by rows and then sends the data out by columns. Nxc3x97D total bytes must be stored in each of two transmit memories of a block interleaver and a total 4xc3x97Nxc3x97D bytes memory area is required for an end-to-end systems (2Nxc3x97D for the transmitter and 2Nxc3x97D for the receiver). Compared to convolutional interleavers, block interleavers are not very efficient in terms of memory use and end-to-end delay. In general, convolutional interleavers reduce the delay and memory by a factor of 2 to 4 for the similar burst error distribution.
For a convolutional interleaver, each of the N bytes Bik in a R-S codeword (say k-th codeword as shown in FIG. 4) is delayed by an amount that varies linearly with the byte index i, where precisely, byte Bik (with index i) is delayed by ixc3x97(Dxe2x88x921) bytes. With the above defined rule, and the chosen interleaving depths, the output bytes from the interleaver always occupy distinct time slots when N and D are co-primed as shown in FIG. 4 with N=15, D=4. When they are not co-primed, dummy bytes are typically added at the beginning of the codeword at the input to the interleaver, and then (Nxe2x88x921) and D are co-primed. The resultant codeword is then convolutionally interleaved, and the dummy byte is removed from the output of the interleaver as in FIG. 5, where N=14, D=4.
The interleaver scheme adopted in ANSI T1.413, and ITU G.992.1/G.992.2 (ADSL) is based on a system originally proposed in Aslanis, J. T., Tong, P. T. and Zogakis, T. N., xe2x80x9cAn ADSL proposal for selectable forward error correction with convolutional interleavingxe2x80x9d, Aug. 20, 1992, TIE1.4: ADSL; and Tong, P. T., Zoagkis, T. N. and Cioffi, J. M., xe2x80x9cRevised FEC and interleaving recommendations for DMT ADSLxe2x80x9d, TIE1.4/93-117, May 1993.
A special type of triangular convolutional interleaver, adopted in the latest ANSI T1E1 VDSL draft, requires that the interleaver depth be D=Nxc3x97M+1, where M is an integer. The implementation requires a memory of (Nxe2x88x921)xc3x97(Dxe2x88x921) bytes, but the constraint on D is very inconvenient for xDSL, when a typical xDSL system uses D less than N. A conventional method of implementing the convolutional interleaver, arranged in a one-dimensional array, is to use a circular buffer of circumference Nxc3x97D. For input byte Bik, the i-th byte in the k-th R-S codeword is as follows:
write address=(kxc3x97N+ixc3x97D)mod Nxc3x97D, for i=0, 1, . . . , Nxe2x88x921,k=0,1, . . . , Dxe2x88x921
read address=(kxc3x97N+i)mod Nxc3x97D, for i=0,1, . . . , Nxe2x88x921, k=0,1, . . . , Dxe2x88x921.
Alternatively, one can also use a Nxc3x97D matrix with n as column index and m as row index as shown in FIGS. 4-5 as follows,
xe2x80x83write address: (n,m)=((ixc3x97D) mod N, (k+ixc3x97D) mod mod D),
read address: (n,m)=(i, k mod D), ∀i=0,1, . . . , Nxe2x88x921, k=0,1, . . . ,Dxe2x88x921.
It can be shown that the memory requirement of the conventional implementation of the convolutional interleaver is Nxc3x97D bytes. Thus, the convolutional interleaver needs no more than half the memory of a block interleaver but twice that of triangular interleaver. As the codeword length and interleaver depth increase for such interleaver systems, the memory requirements become quite significant. As memory requires a significant amount of chip area, it is often necessary to implement such interleavers using multiple integrated circuits, which increases cost, size, and interconnect complexity.
Even in the event the interleaver and memory are included on a single chip, such chips tend to be large. Due to defect density in semiconductor manufacturing, the process yield (i.e., the number of good chips per wafer) is significantly reduced.
Referring now to FIGS. 4 and 5, it should be noted that at any time epoch k almost half of bytes in the memory need not be stored because they have already been transmitted. The memory locations vacated are available for storing new incoming bytes. U. S. Pat. No. 5,764,649 (xe2x80x9cTongxe2x80x9d) discloses a fairly complicated addressing schemexe2x80x94involving reading one byte from an address, writing to the same address, and then calculating the next address. The Tong method can reduce the memory requirement to almost ND/2, which is the theoretical limit. However, the Tong method is unsatisfactory in a number of respects. For example, in order to reduce the memory requirement, the computational-complexity of the algorithm is high and difficult to implement. In particular, this scheme uses at least 3N programmable registers to address the interleaver memory. Thus, there is an intense need for convolutional interleaver designs, which incorporate a more efficient interleaver memory arrangement. More particularly, there is a need for improved convolutional interleaving methods which save memory while significantly reduce programming complexity.
In accordance with one aspect of the present invention, a convolutional interleaver includes an interleaver memory partitioned into a plurality of circular buffers, wherein each of said circular buffers has a write pointer and a read pointer associated therewith, and wherein the interleaver is configured to selectively read symbols from an input vector and store the input symbols in the interleaver memory in accordance with said write pointers, and to selectively read symbols from said interleaver memory to form an output vector in accordance with said read pointers.
In a further aspect of the present invention, symbols are written to the interleaver prior to reading. In accordance with another aspect, the position of the write pointer corresponds to the position of the read pointer within the circular buffer, and symbols are read from said interleaver memory prior to writing. In this way, the size of the interleaver memory can be significantly reduced. More importantly, the present invention approaches the theoretical memory limit with much lower complexity.